//#include <iostream>
//#include <string.h>
//using namespace std;
//
//const int N = 100003;
//int n, ne[N], e[N], idx, h[N];
//
//void insert(int x)
//{
//    int t = (x % N + N) % N;
//    e[idx] = x;
//    ne[idx] = h[t];
//    h[t] = idx++;
//}
//
//bool query(int x)
//{
//    int t = (x % N + N) % N;
//    for (int i = h[t]; i != -1; i = ne[i])
//        if (e[i] == x) return true;
//
//    return false;
//}
//
//int main()
//{
//    cin >> n;
//
//    memset(h, -1, sizeof(h));
//
//    while (n--)
//    {
//        int x;
//        string op;
//        cin >> op >> x;
//        if (op == "I") insert(x);
//        else
//            if (query(x)) cout << "Yes" << endl;
//            else cout << "No" << endl;
//    }
//
//    return 0;
//}
//
// 
// 
//#include <iostream>
//#include <cstring>
//using namespace std;
//
//const int N = 200003, null = 0x3f3f3f3f;
//int h[N], n;
//
//int find(int x)
//{
//    int t = (x % N + N) % N;
//    while (h[t] != null && h[t] != x)
//    {
//        t++;
//        if (t == N) t = 0;
//    }
//
//    return t;
//}
//
//int main()
//{
//    cin >> n;
//    memset(h, 0x3f, sizeof(h));
//
//    while (n--)
//    {
//        int x;
//        string op;
//        cin >> op >> x;
//        if (op == "I") h[find(x)] = x;
//        else
//            if (h[find(x)] != null) cout << "Yes" << endl;
//            else cout << "No" << endl;
//    }
//
//    return 0;
//}
//
// 
// 
//#include <iostream>
//using namespace std;
//
//typedef unsigned long long ULL;
//const int N = 100010, P = 131;
//ULL h[N], p[N];
//int n, m;
//char str[N];
//
//ULL get(int l, int r)
//{
//    return h[r] - h[l - 1] * p[r - l + 1];
//}
//
//int main()
//{
//    scanf("%d%d%s", &n, &m, str + 1);
//
//    p[0] = 1;
//    for (int i = 1; i <= n; i++)
//    {
//        p[i] = p[i - 1] * P;
//        h[i] = h[i - 1] * P + str[i] - 'a' + 1;
//    }
//
//    while (m--)
//    {
//        int l1, r1, l2, r2;
//        cin >> l1 >> r1 >> l2 >> r2;
//        if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
//        else cout << "No" << endl;
//    }
//
//    return 0;
//}



// DFS
//
// ȫ
// 
//#include <iostream>
//using namespace std;
//
//const int N = 10;
//int n;
//int path[N], st[N];
//
//void dfs(int u)
//{
//    if (u == n)
//    {
//        for (int i = 0; i < n; i++) printf("%d ", path[i]);
//        printf("\n");
//        return;
//    }
//
//    for (int i = 1; i <= n; i++)
//        if (!st[i])
//        {
//            path[u] = i;
//            st[i] = 1;
//            dfs(u + 1);
//            st[i] = 0;
//        }
//}
//
//int main()
//{
//    cin >> n;
//
//    dfs(0);
//
//    return 0;
//}

//
//#include <iostream>
//using namespace std;
//
//const int N = 20;
//int col[N], dg[N], udg[N], n;
//char g[N][N];
//
//void dfs(int u)
//{
//    if (u == n)
//    {
//        for (int i = 0; i < n; i++) puts(g[i]);
//        puts("");
//        return;
//    }
//
//    for (int i = 0; i < n; i++)
//    {
//        if (!col[i] && !dg[u + i] && !udg[n - u + i])
//        {
//            g[u][i] = 'Q';
//            col[i] = dg[u + i] = udg[n - u + i] = 1;
//            dfs(u + 1);
//            col[i] = dg[u + i] = udg[n - u + i] = 0;
//            g[u][i] = '.';
//        }
//    }
//}
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//            g[i][j] = '.';
//
//    dfs(0);
//
//    return 0;
//}

